#include <unordered_set>
class Solution {
    unordered_set<string> st;
    vector<string> res;
    vector<bool> vis;
    string path;
public:
    void dfs(string& str, string& path) {
        if (path.size() == str.size()) {
            st.insert(path);
            return;
        }
        for (int i = 0; i < str.size(); ++i) {
            if (vis[i]) continue;
            path += str[i];
            vis[i] = true;
            dfs(str, path);
            path.erase(path.size()-1);
            vis[i] = false;
        }
    }
    vector<string> Permutation(string& str) {
        vis = vector<bool>(str.size(), false);
        dfs(str, path);
        for (auto& str: st) {
            res.push_back(str);
        }
        return res;
    }
};